package com.sourcetrip.raw.adt;


import com.sourcetrip.raw.adt.interfaces.MyMap;
import com.sourcetrip.raw.model.Color;
import com.sourcetrip.raw.model.HashNode;
import com.sourcetrip.raw.model.MyBinaryNode;

/**
 * @author: ZhouBert
 * @date: 2020/12/9
 * @description: 自己设计一个 hashMap
 * 1.拥有一个长度为 64 的 buckets;
 * 2.buckets 的元素是红黑树的 根节点
 * TODO:整体上的优化：
 * 1.由于 node 中 key 的 hash 需要用于 compare ,一旦用于比较就会计算，为了避免大量重复的计算，于是采用了：在node 里保存 hash 的缓存作为变量；
 * 2.覆盖 key 时，需要的条件不是 hashCode 相等，而是 equals() == true !!!
 * 3.继续深入 compare()，比较的顺序是这样的：hashCode - class name - comparable - System.identityHashCode() 利用内存地址算出来的 hashCode 进行比较
 * 也就是说 内存地址的优先级被降低到最后（当作是责任链的最后一环，给了上层的拓展空间）
 * -- 最后发现 用内存地址其实是错误的！因为内存地址的大小是不可预知的！只能老老实实的遍历节点去比较！（也好在情况非常罕见）
 * -- compare 和 equals ：equals 相等能保证 compare ;但是 compare 不能保证 equals
 * 所以不能根据 compare =0 的结果来执行替换！
 * 4.containsValue() 只能一个个去遍历；而 containsKey() 是可以借用buckets 和 红黑树的
 * 5.减法陷阱：不能用减法后的结果与0 的比较来区分大小！因为减去一个负数可能会溢出！！！
 * 6.既然谈到 hashCode ，就应该想到 哈希表，其他的地方用到 hash 的应该不太多！
 * 7.没有比较器时，用 hashCode 去替代 比较的参数【必须有一套比较体系，这样可以提升 hashmap 的性能！】；
 * 8.关于扩容：
 * 我觉得这个也是一个大难题！难点在于如果把之前已经排好序的多个二叉树，在桶索引确定的情况下再分配到新的桶？
 * 从最笨的角度来考虑：将所有的元素重新入一遍。很明显不行，因为这样效率太低了！
 * 然后再想一下，其实只要遍历，计算每个节点的 hashCode ,差不多有近一半的数量是需要重新调整的。会不会JDK 就是用这种方式呢？
 * 此时会有个规律：
 * --> 当扩容为原来容量的2倍时，节点的新索引：要么保持不变，要么 index=index+old size
 * moveNode() 扩容时移动元素时，不可能存在 equals 的元素！所以根本不用判断 equals() + 不用再次遍历元素判断！
 * 9.equals() 的规范：需要保证对称性规范，即 a.equals(b) <=> b.equals(a)
 * 10.LinkedHashMap 结构的删除感觉是很麻烦的！我准备自己实现一遍第一季里面的数据结构！
 */
public class MyHashMap<K, V> implements MyMap<K, V> {

	/**
	 * 容量
	 */
	protected int size;
	/**
	 * buckets 的容量
	 * 这样可以用位运算的 & 来计算 index
	 */
	protected final static int BUCKET_CAPACITY = 64;

	/**
	 * 声明一个 size = 64 的 bucket
	 * 每个元素都是一棵红黑树的根节点！
	 */
	protected HashNode<K, V>[] buckets = new HashNode[BUCKET_CAPACITY];

	/**
	 * constructor
	 */
	public MyHashMap() {
//		for (int i = 0; i < BUCKET_CAPACITY; i++) {
//			buckets[i] =
//		}
	}

	/**
	 * 首先考虑解决[添加]的方法
	 *
	 * @param key
	 * @param value
	 * @return 返回 oldValue
	 */
	@Override
	public V put(K key, V value) {
		int index = getIndex(key);
		boolean flag = addBucket(buckets[index], index, key, value);
		if (flag) {
			size++;
		}
		return value;
	}

	@Override
	public int size() {
		return size;
	}

	/**
	 * TODO:优化：如果 size == 0 -> 不必执行清空操作！
	 */
	@Override
	public void clear() {
		if (size == 0) return;
		size = 0;
		for (int i = 0; i < BUCKET_CAPACITY; i++) {
			buckets[i] = null;
		}
	}


	@Override
	public V get(K key) {
		return null;
	}

	@Override
	public V remove(K key) {
		return null;
	}

	@Override
	public boolean containsKey(K key) {
		return false;
	}

	@Override
	public boolean containsValue(V value) {
		return false;
	}

	@Override
	public void traversal(Visitor<K, V> visitor) {

	}

	//region	中间方法

	/**
	 * 通过 hashCode 找到 bucket 的索引，用于放置元素
	 * by hashcode 取与运算得到
	 * 可以直接拿 int 做 & 运算
	 * TODO: 改进：应该传一个对象，因为是允许传 null 的，当 key == null 时，桶索引 = 0
	 *
	 * @param hashCode int 型
	 * @return 桶中的索引
	 */
	private int getIndex(int hashCode) {
		int index = hashCode & (BUCKET_CAPACITY - 1);
		return index;
	}

	/**
	 * TODO:关于 jdk 里的写法：(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
	 * 为何要无符号右移 16 位，让高位参与运算呢？
	 * 至于为何16位先不管，但是由于 最后的桶索引的位置取决于最后的几位，
	 * （当buckets.length=8时,下标运算结果取决于哈希值的低三位）
	 * （当buckets.length=16时,下标运算结果取决于哈希值的低四位）
	 * 所以让高位参与运算，可以让 hashValue 更加散列！
	 *
	 * @param key
	 * @return
	 */
	private int getIndex(K key) {
		//1.如果 对象为 null -> 桶索引=0
		if (key == null) {
			return 0;
		}
		return getIndex(key.hashCode());
	}


	/**
	 * @param root
	 * @param index buckets 的索引
	 * @param key
	 * @param value
	 */
	private boolean addBucket(HashNode<K, V> root, int index, K key, V value) {
		//1.该桶位置还未添加元素
		if (root == null) {
			root = new HashNode<K, V>(key, null, value);
			root.setColor(Color.BLACK);
			buckets[index] = root;
			return true;
		}
		//2.如果已经有元素，那就作为一棵红黑树，注意，这里的红黑树不需要比较器！
		//那么用来比较的就是 hashCode !!!
		HashNode<K, V> cur = root;
		HashNode<K, V> prev = null;
		while (cur != null) {
			//找到 key 相等 -> 进行 value 替换
			if (cur.getElement().hashCode() == key.hashCode()) {
				cur.setValue(value);
				return false;
			}
			prev = cur;
			//往左走
			if (cur.getElement().hashCode() > key.hashCode()) {
				cur = (HashNode<K, V>) cur.getLeft();
			} else {
				cur = (HashNode<K, V>) cur.getRight();
			}
		}
		//此时 cur 就是该放 key 的位置
		cur = new HashNode<>(key, prev, value);
		// 默认 红色
		cur.setColor(Color.RED);
		if (cur.isLeftChild()) {
			prev.setLeft(cur);
		} else {
			prev.setRight(cur);
		}
		//红黑树添加后的调整
		afterAdd(root, cur, prev);
		return true;
	}

	/**
	 * @param root   红黑树的根节点
	 * @param node   添加后的节点
	 * @param parent 添加后的节点的父节点
	 */
	private void afterAdd(HashNode<K, V> root, HashNode<K, V> node, HashNode<K, V> parent) {
		//1.parent is BLACK
		if (isBlack(parent)) {
			return;
		}

		HashNode<K, V> grand = (HashNode<K, V>) parent.getParent();
		//2.parent is RED && parent 兄弟节点 is Black
		if (isBlack(parent.sibling())) {
			//parent is left child
			if (parent.isLeftChild()) {
				//L
				if (node.isLeftChild()) {
					//LL
					//parent 右边移动(grand 右旋)
					rotateRight(grand, root);
					//1.black(parent)
					parent.setColor(Color.BLACK);
					//2.red(grand)
					grand.setColor(Color.RED);
				} else {
					//LR
					//1.parent 左旋
					rotateLeft(parent, root);
					//2.grand 右旋
					rotateRight(grand, root);
					//3.black(node)
					node.setColor(Color.BLACK);
					//4.red(grand)
					grand.setColor(Color.RED);
				}
			} else {
				//R
				if (node.isLeftChild()) {
					//RL
					//1.parent 右旋
					rotateRight(parent, root);
					//2.grand 左旋
					rotateLeft(grand, root);
					//3.black(node)
					node.setColor(Color.BLACK);
					//4.red(grand)
					grand.setColor(Color.RED);
				} else {
					//RR
					rotateLeft(grand, root);
					//1.black(parent)
					parent.setColor(Color.BLACK);
					//2.red(grand)
					grand.setColor(Color.RED);
				}
			}
		}
	}

	/**
	 * 判断红黑树的节点是否为 黑
	 * 由于节点为 null 时 -> BLACK ，所以放在本类中作为判断颜色才是完整的
	 *
	 * @param node
	 * @return
	 */
	private boolean isBlack(HashNode<K, V> node) {
		return node == null || node.isBlack();
	}

	/**
	 * 判断红黑树的节点是否为 红
	 *
	 * @param node
	 * @return
	 */
	private boolean isRed(HashNode<K, V> node) {
		return node != null && node.isRed();
	}

	/**
	 * 将 node 节点左旋
	 *
	 * @param grand 需要旋转的节点
	 * @param root  根节点
	 */
	private void rotateLeft(HashNode<K, V> grand, HashNode<K, V> root) {
		HashNode<K, V> prev = (HashNode<K, V>) grand.getParent();
		HashNode<K, V> parent = (HashNode<K, V>) grand.getRight();
		MyBinaryNode<K> leftChild = parent.getLeft();
		if (prev == null) {
			root = parent;
		} else {
			if (grand.isLeftChild()) {
				prev.setLeft(parent);
			} else {
				prev.setRight(parent);
			}
			parent.setParent(prev);
		}
		parent.setLeft(grand);
		grand.setRight(leftChild);
		grand.setParent(parent);

		if (leftChild != null) {
			leftChild.setParent(grand);
		}
		return;
	}

	/**
	 * 将 node 节点右旋
	 *
	 * @param grand 需要旋转的节点
	 * @param root  根节点
	 */
	private void rotateRight(HashNode<K, V> grand, HashNode<K, V> root) {
		HashNode<K, V> prev = (HashNode<K, V>) grand.getParent();
		HashNode<K, V> parent = (HashNode<K, V>) grand.getLeft();
		MyBinaryNode<K> rightChild = parent.getRight();
		if (prev == null) {
			root = parent;
		} else {
			if (grand.isLeftChild()) {
				prev.setLeft(parent);
			} else {
				prev.setRight(parent);
			}
			parent.setParent(prev);
		}
		parent.setLeft(grand);
		grand.setLeft(rightChild);
		grand.setParent(parent);

		if (rightChild != null) {
			rightChild.setParent(grand);
		}
		return;
	}


	//endregion
}
